package datastructure.book.tujiesuanfa.tree.more;

import datastructure.book.tujiesuanfa.tree.bean.Node;
import datastructure.book.tujiesuanfa.tree.bean.TreeNode;

import java.util.List;

public class Solution1 {

    /**
     * 第一层从左往右遍历，其余每层遍历顺序与上一层相反，每一层的结果放在一个list里
     * 第一层：从左往右、第二层：从右往左、第三层：从左往右
     */
    public List<List<Integer>> decorateRecord(TreeNode root) {
        return null;
    }

    /**
     * 两棵二叉树 tree1 和 tree2，
     * 判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值
     * tree2为空返回false
     * tree1:
     *        [3]
     *    [6]     [7]
     * [1]  [8] []  []
     * tree2:
     *         [6]
     *       [1]  []
     * tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。
     */
    public boolean isSubStructure(TreeNode A, TreeNode B){
        return false;
    }

    /**
     * 将二叉搜索树转化为排序的双向链表
     * 将左右孩子指针作为双向循环链表的前驱和后继指针，
     * 第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点
     * 返回链表中最小元素的指针
     * Node.left.val < Node.val < Node.right.val
     *              4
     *      2               7
     *   1     3        6       8
     *               5
     *   [8]<=>1<=>2<=>3<=>4<=>5<=>6<=>7<=>8<=>[1]
     */
    public Node treeToDoublyList(Node root) {
        return null;
    }

    /**
     * 判断是否为平衡二叉树
     * 二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树
     * 例：平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     * 非平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     *       3
     */
    public boolean isBalanced(TreeNode root) {
        return false;
    }

    /**
     * 寻找二叉树的最近公共祖先
     * 例：3   8 最近公共祖先为 -1
     *           -1
     *       0         3
     *   -2    4
     * 8
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return null;
    }
}
